package leetcode_900;

import java.util.ArrayList;
import java.util.List;

/**
 *@author 周杨
 *OnlineStockSpan_901 实现一种数组结构 它能输出它之前的连续的比它小或者等的数 的数量
 *describe:用左指针 AC 63%
 *2018年11月13日 下午3:05:33
 */
public class OnlineStockSpan_901 {
		public static void main(String[] args) {
			OnlineStockSpan_901 test=new OnlineStockSpan_901();
			System.out.println(test.next(31));
			System.out.println(test.next(41));
			System.out.println(test.next(48));
			System.out.println(test.next(59));
			System.out.println(test.next(79));
		}
	
	 	List<Integer> elements;
	 	List<Integer> counts;
	 	public OnlineStockSpan_901() {
	        this.elements=new ArrayList<Integer>();
	        this.counts=new ArrayList<Integer>();
	    }
	    
	    public int next(int price) {
	        if(elements.size()==0) {
	        	this.elements.add(price);
	        	this.counts.add(1);//没有数比它大
	        	return 1;
	        }
	        else {
	        	//直到遇到比它大的数 保存所有小于等于它的数的个数
	        	int ele=elements.get(elements.size()-1);
	        	int index=counts.size()-1;
	        	while(price>=ele) {
	        		index-=counts.get(index);
	        		if(index<0)
	        			break;
	        		ele=elements.get(index);
	        	}
	        	this.elements.add(price);
	        	this.counts.add(counts.size()-index);
	        	return counts.size()-index-1;//因为增加了1
	        }
	    }
}
